package com.he.algorithm.order;

import java.util.Arrays;

/**
 * @description: TODO
 * @Author: HCL
 * @Date: 2024/9/12 15:57
 */
public class ShellSort {

    private static void sort(int[] nums) {
        int gap = nums.length / 2;
        while (gap > 0){
            for (int i = gap; i < nums.length; i++) {
                int key = nums[i];//当前需要排序到正确位置的元素
                int j = i - gap;// 插入位置的起始点
                // 寻找插入位置，并将比current大的元素向后移动
                while (j >= 0 && nums[j] > key) {
                    nums[j + gap] = nums[j];
//                    j = j - gap;
                    j -= gap;
                }
                nums[j + gap] = key;// 插入current到正确位置
            }
//            gap = gap / 2;
            gap /= 2;
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 6, 7, 8, 9};
        sort(nums);
        System.out.println(Arrays.toString(nums));
    }
}
